﻿#include <iostream>

typedef char TElemType;
TElemType Nil = '#';
#define MaxTreeSize 4

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;


void InitBiTree(BiTree &BT) {
    BT = NULL;
}

void CreatBiTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == Nil)
        BT = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!BT) exit(-1); // 申请新结点失败
        BT->data = e;
        CreatBiTree(BT->lchild);  // 递归构造左子树
        CreatBiTree(BT->rchild);  // 递归构造右子树
    }
}

void Visit(BiTree BT) {
    printf("%c", BT->data);
}

int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}


/*
 * 二叉树按照二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有双分枝结点个数。
 * 操作步骤：设计一个计数器和栈，栈用来保存刚刚访问的结点，当这个结点的左子树和右子树不为空，则count加一，直到整个结点都遍历过。
 */
int DoubleNodeCount(BiTree BT) {
    if (BT == NULL)
        return 0;
    BiTNode *p;
    BiTNode *stack[MaxTreeSize];
    int count = 0, top = -1;
    stack[++top] = BT;  // 根结点压栈
    while (top > -1){   // 栈非空
        p = stack[top--];  // 栈顶元素出栈
        if (p->lchild != NULL && p->rchild != NULL)
            count++;  // p指向的结点有双分枝，计算器加一
        if (p->rchild != NULL)
            stack[++top] = p->rchild;
        if (p->lchild != NULL) {
                stack[++top] = p->lchild;
        }
    }
    return count;
}


int main() {
    BiTree BT;
    InitBiTree(BT);
    printf("创建一棵二叉树,请按照前序序列输入树中的结点（'#'表示子树为空）：\n");
    CreatBiTree(BT);

    printf("双分支结点个数为：");
    int count = DoubleNodeCount(BT);
    printf("%d", count);

    return 0;
}